/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\146.lru-缓存机制.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-26 10:42:16
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-26 18:12:45
 */
/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU 缓存机制
 */

// @lc code=start
// class LRUCache {
// private:
//     list<pair<int,int>> cache;
//     unordered_map<int,list<pair<int,int>>::iterator> key2node;
//     int cap;
// public:
//     LRUCache(int capacity) :cap(capacity){

//     }

//     int get(int key) {
//         if(key2node.find(key) == key2node.end())
//         {
//             return -1;
//         }
//         pair<int,int> node = *key2node[key];
//         cache.erase(key2node[key]);
//         cache.push_front(node);
//         key2node[key] = cache.begin();
//         return node.second;
//     }

//     void put(int key, int value) {
//         auto newNode = std::make_pair(key,value);
//         if(key2node.count(key))
//         {
//             cache.erase(key2node[key]);
//         }
//         else
//         {
//             if(cap == cache.size())
//             {
//                 key2node.erase(cache.back().first);
//                 cache.pop_back();
//             }
//         }

//         cache.push_front(newNode);
//         key2node[key] = cache.begin();
//     }
// };

class Node
{
public:
    int key;
    int val;
    Node *left;
    Node *right;

    Node(int k,int v):key(k),val(v){};
};

class Queuelist
{

public:
    Node* head;
    Node* tail;

    Queuelist()
    {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head->right = tail;
        tail->left = head;
    }

    // 在头部插入一个元素
    void insertAsfirst(Node *node)
    {
        node->left = head;
        node->right = head->right;
        head->right = node;
        node->right->left = node;
    }

    // 删除一个节点
    void remove(Node* node){
        node->left->right = node->right;
        node->right->left = node->left;
        
        delete node;
    }
    Node *getLastNode(){

        return tail->left;
    }

};

class LRUCache
{
int cap;
int size;
unordered_map<int,Node *> map;
Queuelist cache;

public:
    LRUCache(int capacity) :cap(capacity),size(0){

    }
    int get(int key)
    {
        if(map.count(key) == 0)
        {
            // 表示没有对应的节点
            return -1;
        }
        // 返回有值的节点，并将节点放置在head后面
        Node *node = map[key];
        int val = node->val;
        Node *tmp = new Node(key,val);
        cache.remove(node);
        cache.insertAsfirst(tmp);
        map[key] = tmp;
        return val;
    }

    void put(int key,int value)
    {
       
       if(map.count(key) == 0)
       {
           Node *node = new Node(key,value);
           // 没有这个元素
           if(size == cap)
           {
               // 队列是满的，需要删除最后一个，插入一个新的
               Node *lastnode = cache.getLastNode();
               map.erase(lastnode->key);                    // 将这个要删除的节点从map中删除
               cache.remove(lastnode);
               cache.insertAsfirst(node);
               map[key] = node;                       // 将新节点插入到map中
           }
           else{
               map[key] = node;
               cache.insertAsfirst(node);
               size++;
           }
       }
    //    else
       {
           // 链表中存在这个元素
           get(key);
           map[key]->val = value;
       }
    }
};

// class Node
// {
// public:
//     int key;
//     int value;
//     Node *left;
//     Node *right;

//     Node(int key, int value) : key(key), value(value)
//     {
//     }
// };

// // 由左往右，最新的数据插在最左边，达到capacity删除最后边的节点
// class doubleList
// {
//     Node *head;
//     Node *tail;

// public:
//     doubleList()
//     {
//         head = new Node(-1, -1);
//         tail = new Node(-1, -1);
//         head->right = tail;
//         tail->left = head;
//     }

//     // 插到最前面
//     void insertAsFirst(Node *node)
//     {
//         node->left = head;
//         node->right = head->right;
//         head->right = node;
//         node->right->left = node;
//     }

//     // O(1)时间删除一个节点
//     void remove(Node *node)
//     {
//         node->left->right = node->right;
//         node->right->left = node->left;
//         delete node;
//     }

//     // 返回最后一个节点
//     Node *getLastNode()
//     {
//         return tail->left;
//     }
// };

// class LRUCache
// {
//     int cap;
//     int size;
//     unordered_map<int, Node *> mp;
//     doubleList cache;

// public:
//     LRUCache(int capacity)
//     {
//         this->cap = capacity;
//         this->size = 0;
//     }

//     int get(int key)
//     {
//         // 如果没有，直接返回-1
//         if (mp.count(key) == 0)
//         {
//             return -1;
//         }
//         // 找到原节点删除后，插入新节点
//         Node *tmp = mp[key];
//         int val = tmp->value;
//         Node *node = new Node(key, val);
//         cache.remove(tmp);
//         mp[key] = node;
//         cache.insertAsFirst(node);
//         return val;
//     }

//     void put(int key, int value)
//     {
//         // c查看是否存在
//         if (mp.count(key) == 0)
//         {
//             Node *node = new Node(key, value);
//             if (cap == size)
//             {
//                 Node *tmp = cache.getLastNode();
//                 mp.erase(tmp->key);
//                 cache.remove(tmp);
//                 mp[key] = node;
//                 cache.insertAsFirst(node);
//             }
//             else
//             {
//                 mp[key] = node;
//                 cache.insertAsFirst(node);
//                 this->size++;
//             }
//         }
//         else
//         {
//             get(key);
//             // 不要忘了修改value
//             mp[key]->value = value;
//         }
//     }
// };

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end
